🧮
DS_ALGO Practice:
GitHub - bgoonz/Leetcode-JS-PY-MD
GitHub
https://bgoonz.github.io/Leetcode-JS-PY-MD
JS
1
/**
2
* ███████████████═╗ ███████████████═╗ █████████████═╗ █████═╗ █████═╗
3
* ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║
4
* ╚═══█████ ╔════╝ ╚═══█████ ╔════╝ █████ ╔═════════╝ █████ ║ █████ ║
5
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
6
* █████ ║ █████ ║ █████████████═╗ ███████████████ ║
7
* █████ ║ █████ ║ ╚█████████████═╗ ╚███████████ ╔═╝
8
* █████ ║ █████ ║ ╚══════█████ ║ ╚═█████ ╔══╝
9
* █████ ║ █████ ║ █████ ║ █████ ║
10
* ███████████████═╗ █████ ║ ███████████████ ║ █████ ║
11
* ███████████████ ║ █████ ║ █████████████ ╔═╝ █████ ║
12
* ╚══════════════╝ ╚════╝ ╚════════════╝ ╚════╝
13
*
14
* █████████████═══╗ ███████████████═╗ ███████████████═╗ █████████████═╗ █████═╗ █████═╗
15
* ███████████████ ║ ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║
16
* █████ ╔═══█████ ║ ╚═══█████ ╔════╝ ╚═══█████ ╔════╝ █████ ╔═════════╝ █████ ║ █████ ║
17
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
18
* █████████████ ╔═╝ █████ ║ █████ ║ █████████████═╗ ███████████████ ║
19
* ███████████████═╗ █████ ║ █████ ║ ╚█████████████═╗ ╚███████████ ╔═╝
20
* █████ ╔═══█████ ║ █████ ║ █████ ║ ╚══════█████ ║ ╚═█████ ╔══╝
21
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
22
* ███████████████ ║ ███████████████═╗ █████ ║ ███████████████ ║ █████ ║
23
* █████████████ ╔═╝ ███████████████ ║ █████ ║ █████████████ ╔═╝ █████ ║
24
* ╚════════════╝ ╚══════════════╝ ╚════╝ ╚════════════╝ ╚════╝
25
*
26
* █████████████═══╗ ███████████═══╗ ███████████████═╗ ███████████═══╗
27
* ███████████████ ║ ███████████████ ║ ███████████████ ║ ███████████████ ║
28
* █████ ╔═══█████ ║ █████ ╔═══█████ ║ ╚═══█████ ╔════╝ █████ ╔═══█████ ║
29
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
30
* █████ ║ █████ ║ ███████████████ ║ █████ ║ ███████████████ ║
31
* █████ ║ █████ ║ ███████████████ ║ █████ ║ ███████████████ ║
32
* █████ ║ █████ ║ █████ ╔═══█████ ║ █████ ║ █████ ╔═══█████ ║
33
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
34
* ███████████████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
35
* █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
36
* ╚════════════╝ ╚════╝ ╚════╝ ╚════╝ ╚════╝ ╚════╝
37
*
38
* █████████████═╗ ███████████████═╗ █████████████═══╗ █████═╗ █████═╗ █████████████═╗ ███████████████═╗
39
* ███████████████ ║ ███████████████ ║ ███████████████ ║ █████ ║ █████ ║ ███████████████ ║ ███████████████ ║
40
* █████ ╔═════════╝ ╚═══█████ ╔════╝ █████ ╔═══█████ ║ █████ ║ █████ ║ █████ ╔═════════╝ ╚═══█████ ╔════╝
41
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
42
* █████████████═╗ █████ ║ █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ █████ ║
43
* ╚█████████████═╗ █████ ║ ███████████████═╗ █████ ║ █████ ║ █████ ║ █████ ║
44
* ╚══════█████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
45
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
46
* ███████████████ ║ █████ ║ █████ ║ █████ ║ ███████████████ ║ ███████████████═╗ █████ ║
47
* █████████████ ╔═╝ █████ ║ █████ ║ █████ ║ ╚███████████ ╔═╝ ╚█████████████ ║ █████ ║
48
* ╚════════════╝ ╚════╝ ╚════╝ ╚════╝ ╚══════════╝ ╚════════════╝ ╚════╝
49
*
50
* █████═╗ █████═╗ █████████████═══╗ ████████████████═╗ ██████████████═╗
51
* █████ ║ █████ ║ ███████████████ ║ ████████████████ ║ ████████████████ ║
52
* █████ ║ █████ ║ █████ ╔═══█████ ║ █████ ╔══════════╝ █████ ╔══════════╝
53
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
54
* █████ ║ █████ ║ █████████████ ╔═╝ ████████████████═╗ ██████████████═╗
55
* █████ ║ █████ ║ ███████████████═╗ ████████████████ ║ ╚██████████████═╗
56
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ╔══════════╝ ╚═══════█████ ║
57
* █████ ║ █████ ║ █████ ║ █████ ║ █████ ║ █████ ║
58
* ███████████████ ║ █████ ║ █████ ║ ████████████████═╗ ████████████████ ║
59
* ╚███████████ ╔═╝ █████ ║ █████ ║ ████████████████ ║ ██████████████ ╔═╝
60
* ╚══════════╝ ╚════╝ ╚════╝ ╚═══════════════╝ ╚═════════════╝
61
*
62
*/
63
64
/**
65
* Today we're gonna learn all about data structures.
66
*
67
* "OOooooOOOooh *soo* exciting" right?
68
*
69
* Yeah, they definitely aren't the juiciest topic out there, but they are
70
* important. Not just to pass computer science 101, but in order to be a
71
* better programmer.
72
*
73
* Knowing your data structures can help you:
74
*
75
* - Manage complexity and make your programs easier to follow.
76
* - Build high-performance, memory-efficient programs.
77
*
78
* I believe that the former is more important. Using the right
79
* data structure can drastically simplify what would otherwise
80
* be complicated logic.
81
*
82
* The latter is important too. If performance or memory matters then
83
* using the right data structure is more than often essential.
84
*
85
* In order to learn about data structures, we're going to implement a few of
86
* them together. Don't worry, we'll keep the code nice and short. In fact,
87
* there are way more comments than there is code.
88
*/
89
90
/**
91
* ============================================================================
92
* ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
93
* ============================================================================
94
*/
95
96
/**
97
* What are data structures?
98
*
99
* Essentially, they are different methods of storing and organizing data that
100
* serve a number of different needs.
101
*
102
* Data can always be represented in many different ways. However, depending on
103
* what that data is and what you need to do with it, one representation will
104
* be a better choice than the others.
105
*
106
* To understand why let's first talk a bit about algorithms.
107
*/
108
109
/*** ===================================================================== ***\
110
** - ALGORITHMS ---------------------------------------------------------- **
111
* ========================================================================= *
112
* *
113
* ,--,--. ,--,--. *
114
* ,----------. | | | | | | _____ *
115
* |`----------'| | | | | | | | | ,------. *
116
* | | | | | | | | ,--. | o o | |`------'| *
117
* | | ,| +-|-+ | | +-|-+ |` | | |_____| | | *
118
* | | ,:==| | |###|======|###| | |====#==#====#=,, | | *
119
* | | || `| +---+ | | +---+ |' ,,=#==#====O=`` ,| | *
120
* | | || | | | | | | ``=#==#====#=====|| | *
121
* `----------' || | | | | | | |__| `| | *
122
* | | ``=| |===`` `--,',--` `--,',--` /||\ `------' *
123
** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| **
124
\*** ===================================================================== ***/
125
126
/**
127
* Algorithm is a fancy name for step-by-step sets of operations to be
128
* performed.
129
*
130
* Data structures are implemented with algorithms, and algorithms are
131
* implemented with data structures. It's data structures and algorithms all
132
* the way down until you reach the microscopic people with punch cards that
133
* control the computer. (That's how computers work right?)
134
*
135
* Any given task can be implemented in an infinite number of ways. So for
136
* common tasks there are often many different algorithms that people have come up
137
* with.
138
*
139
* For example, there are an absurd number of algorithms for sorting a set of
140
* unordered items:
141
*
142
* Insertion Sort, Selection Sort, Merge Sort, Bubble Sort, Heap Sort,
143
* Quick Sort, Shell Sort, Timsort, Bucket Sort, Radix Sort, ...
144
*
145
* Some of these are significantly faster than others. Some use less memory.
146
* Some are easy to implement. Some are based on assumptions about the dataset.
147
*
148
* Every single one of them will be better for *something*. So you'll need to
149
* make a decision based on what your needs are and for that, you'll need a way
150
* of comparing them, a way to measure them.
151
*
152
* When we compare the performance of algorithms we use a rough measurement of
153
* their average and worst-case performance using something called "Big-O".
154
*/
155
156
/*** ===================================================================== ***\
157
** - BIG-O NOTATION ------------------------------------------------------ **
158
* ========================================================================= *
159
* a b d *
160
* a b O(N^2) d *
161
* O(N!) a b O(N log N) d c *
162
* a b d c *
163
* a b d c O(N) *
164
* a b d c *
165
* a b d c *
166
* a b d c *
167
* ab c O(1) *
168
* e e e e ec d e e e e e e e e *
169
* ba c d *
170
* ba c d f f f f f f f *
171
** cadf f d f f f f f O(log N) **
172
\*** ===================================================================== ***/
173
174
/**
175
* Big-O Notation is a way of roughly measuring the performance of algorithms
176
* in order to compare one against another when discussing them.
177
*
178
* Big-O is a mathematical notation that we borrowed in computer science to
179
* classify algorithms by how they respond to the number (N) of items that you
180
* give them.
181
*
182
* There are two primary things that you measure with Big-O:
183
*
184
* - **Time complexity** refers to the total count of operations an algorithm
185
* will perform given a set of items.
186
*
187
* - **Space complexity** refers to the total memory an algorithm will take up
188
* while running given a set of items.
189
*
190
* We measure these independently from one another because while an algorithm
191
* may perform fewer operations than another, it may also take up way more
192
* memory. Depending on what your requirements are, one may be a better choice
193
* than the other.
194
*
195
* These are some common Big-O's:
196
*
197
* Name Notation How you feel when they show up at your party
198
* ------------------------------------------------------------------------
199
* Constant O(1) AWESOME!!
200
* Logarithmic O(log N) GREAT!
201
* Linear O(N) OKAY.
202
* Linearithmic O(N log N) UGH...
203
* Polynomial O(N ^ 2) SHITTY
204
* Exponential O(2 ^ N) HORRIBLE
205
* Factorial O(N!) WTF
206
*
207
* To give you an idea of how many operations we're talking about. Let's look
208
* at what these would equal given the (N) number of items.
209
*
210
* N = 5 10 20 30
211
* -----------------------------------------------------------------------
212
* O(1) 1 1 1 1
213
* O(log N) 2.3219... 3.3219... 4.3219... 4.9068...
214
* O(N) 5 10 20 30
215
* O(N log N) 11.609... 33.219... 84.638... 147.204...
216
* O(N ^ 2) 25 100 400 900
217
* O(2 ^ N) 32 1024 1,048,576 1,073,741,824
218
* O(N!) 120 3,628,800 2,432,902,0... 265,252,859,812,191,058,636,308,480,000,000
219
*
220
* As you can see, even for relatively small sets of data you could do
221
* a **lot** of extra work.
222
*
223
* With data structures, you can perform 4 primary types of actions:
224
* Accessing, Searching, Inserting, and Deleting.
225
*
226
* It is important to note that data structures may be good at one action but
227
* bad at another.
228
*
229
* Accessing Searching Inserting Deleting
230
* -------------------------------------------------------------------------
231
* Array O(1) O(N) O(N) O(N)
232
* Linked List O(N) O(N) O(1) O(1)
233
* Binary Search Tree O(log N) O(log N) O(log N) O(log N)
234
*
235
* Or rather...
236
*
237
* Accessing Searching Inserting Deleting
238
* -------------------------------------------------------------------------
239
* Array AWESOME!! OKAY OKAY OKAY
240
* Linked List OKAY OKAY AWESOME!! AWESOME!!
241
* Binary Search Tree GREAT! GREAT! GREAT! GREAT!
242
*
243
* Even further, some actions will have a different "average" performance and a
244
* "worst case scenario" performance.
245
*
246
* There is no perfect data structure, and you choose one over another based on
247
* the data that you are working with and the things you are going to do with
248
* it. This is why it is important to know a number of different common data
249
* structures so that you can choose from them.
250
*/
251
252
/*** ===================================================================== ***\
253
** - MEMORY -------------------------------------------------------------- **
254
* ========================================================================= *
255
* _.-.. *
256
* ,'9 )\)`-.,.--. *
257
* `-.| `. *
258
* \, , \) *
259
* `. )._\ (\ *
260
* |// `-,// *
261
* ]|| //" *
262
** hjw "" "" **
263
\*** ===================================================================== ***/
264
265
/**
266
* A computer's memory is pretty boring, it's just a bunch of ordered slots
267
* where you can store information. You hold onto memory addresses in order to
268
* find information.
269
*
270
* Let's imagine a chunk of memory like this:
271
*
272
* Values: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011...
273
* Addresses: 0 1 2 3 4 5 6 7 8 9 ...
274
*
275
* If you've ever wondered why things are zero-indexed in programming languages
276
* before, it is because of the way that memory works. If you want to read the
277
* first chunk of memory you read from 0 to 1, the second you read from 1 to 2.
278
* So the address that you hold onto for each of those is 0 and 1 respectively.
279
*
280
* Your computer has much much more memory than this, and it is all just a
281
* continuation of the pattern above.
282
*
283
* Memory is a bit like the wild west, every program running on your machine is
284
* stored within this same *physical* data structure. Without layers of
285
* abstraction over it, it would be extremely difficult to use.
286
*
287
* But these abstractions serve two additional purposes:
288
*
289
* - Storing data in memory in a way that is more efficient and/or faster to
290
* work with.
291
* - Storing data in memory in a way that makes it easier to use.
292
*/
293
294
/*** ===================================================================== ***\
295
** - LISTS --------------------------------------------------------------- **
296
* ========================================================================= *
297
* * _______________________ *
298
* ()=(_______________________)=() * *
299
* * | | *
300
* | ~ ~~~~~~~~~~~~~ | * * *
301
* * | | *
302
* * | ~ ~~~~~~~~~~~~~ | * *
303
* | | *
304
* | ~ ~~~~~~~~~~~~~ | * *
305
* * | | *
306
* * |_____________________| * * *
307
* ()=(_______________________)=() *
308
** **
309
\*** ===================================================================== ***/
310
311
/**
312
* To demonstrate the raw interaction between memory and a data structure we're
313
* going to first implement a list.
314
*
315
* A list is a representation of an ordered sequence of values where the same
316
* value may appear many times.
317
*/
318
319
class List {
320
321
/**
322
* We start with an empty block of memory which we are going to represent
323
* with a normal JavaScript array and we'll store the length of the list.
324
*
325
* Note that we want to store the length separately because in real life the
326
* "memory" doesn't have a length you can read from.
327
*/
328
329
constructor() {
330
this.memory = [];
331
this.length = 0;
332
}
333
334
/**
335
* First we need a way to retrieve data from our list.
336
*
337
* With a plain list, you have very fast memory access because you keep track
338
* of the address directly.
339
*
340
* List access is constant O(1) - "AWESOME!!"
341
*/
342
343
get(address) {
344
return this.memory[address];
345
}
346
347
/**
348
* Because lists have an order you can insert stuff at the start, middle,
349
* or end of them.
350
*
351
* For our implementation, we're going to focus on adding and removing values
352
* at the start or end of our list with these four methods:
353
*
354
* - Push - Add value to the end
355
* - Pop - Remove a value from the end
356
* - Unshift - Add value to the start
357
* - Shift - Remove a value from the start
358
*/
359
360
/*
361
* Starting with "push" we need a way to add items to the end of the list.
362
*
363
* It is as simple as adding a value in the address after the end of our
364
* list. Because we store the length this is easy to calculate. We just add
365
* the value and increment our length.
366
*
367
* Pushing an item to the end of a list is constant O(1) - "AWESOME!!"
368
*/
369
370
push(value) {
371
this.memory[this.length] = value;
372
this.length++;
373
}
374
375
/**
376
* Next we need a way to "pop" items off of the end of our list.
377
*
378
* Similar to push all we need to do is remove the value at the address at
379
* the end of our list. Then just decrement length.
380
*
381
* Popping an item from the end of a list is constant O(1) - "AWESOME!!"
382
*/
383
384
pop() {
385
// Don't do anything if we don't have any items.
386
if (this.length === 0) return;
387
388
// Get the last value, stop storing it, and return it.
389
let lastAddress = this.length - 1;
390
let value = this.memory[lastAddress];
391
delete this.memory[lastAddress];
392
this.length--;
393
394
// Also return the value so it can be used.
395
return value;
396
}
397
398
/**
399
* "push" and "pop" both operate on the end of a list, and overall are pretty
400
* simple operations because they don't need to be concerned with the rest of
401
* the list.
402
*
403
* Let's see what happens when we operate at the beginning of the list with
404
* "unshift" and "shift".
405
*/
406
407
/**
408
* In order to add a new item at the beginning of our list, we need to make
409
* room for our value at the start by sliding all of the values over by one.
410
*
411
* [a, b, c, d, e]
412
* 0 1 2 3 4
413
* ⬊ ⬊ ⬊ ⬊ ⬊
414
* 1 2 3 4 5
415
* [x, a, b, c, d, e]
416
*
417
* In order to slide all of the items over we need to iterate over each one
418
* moving the prev value over.
419
*
420
* Because we have to iterate over every single item in the list:
421
*
422
* Unshifting an item to the start of a list is linear O(N) - "OKAY."
423
*/
424
425
unshift(value) {
426
// Store the value we are going to add to the start.
427
let previous = value;
428
429
// Iterate through each item...
430
for (let address = 0; address < this.length; address++) {
431
// replacing the "current" value with the "previous" value and storing the
432
// "current" value for the next iteration.
433
let current = this.memory[address];
434
this.memory[address] = previous;
435
previous = current;
436
}
437
438
// Add the last item in a new position at the end of the list.
439
this.memory[this.length] = previous;
440
this.length++;
441
}
442
443
/**
444
* Finally, we need to write a shift function to move in the opposite
445
* direction.
446
*
447
* We delete the first value and then slide through every single item in the
448
* list to move it down one address.
449
*
450
* [x, a, b, c, d, e]
451
* 1 2 3 4 5
452
* ⬋ ⬋ ⬋ ⬋ ⬋
453
* 0 1 2 3 4
454
* [a, b, c, d, e]
455
*
456
* Shifting an item from the start of a list is linear O(N) - "OKAY."
457
*/
458
459
shift() {
460
// Don't do anything if we don't have any items.
461
if (this.length === 0) return;
462
463
let value = this.memory[0];
464
465
// Iterate through each item...
466
for (let address = 0; address < this.length - 1; address++) {
467
// and replace them with the next item in the list.
468
this.memory[address] = this.memory[address + 1];
469
}
470
471
// Delete the last item since it is now in the previous address.
472
delete this.memory[this.length - 1];
473
this.length--;
474
475
return value;
476
}
477
}
478
479
/**
480
* Lists are great for fast access and dealing with items at the end. However,
481
* as we've seen it isn't great at dealing with items not at the end of the
482
* list and we have to manually hold onto memory addresses.
483
*
484
* So let's take a look at a different data structure and how it deals with
485
* adding, accessing, and removing values without needing to know memory
486
* addresses.
487
*/
488
489
/*** ===================================================================== ***\
490
** - HASH TABLES --------------------------------------------------------- **
491
* ========================================================================= *
492
* ((\ *
493
* ( _ ,-_ \ \ *
494
* ) / \/ \ \ \ \ *
495
* ( /)| \/\ \ \| | .'---------------------'. *
496
* `~()_______)___)\ \ \ \ \ | .' '. *
497
* |)\ ) `' | | | .'-----------------------------'. *
498
* / /, | '...............................' *
499
* ejm | | / \ _____________________ / *
500
* \ / | |_) (_| | *
501
* \ / | | | | *
502
* ) / | | | | *
503
** / / (___) (___) **
504
\*** ===================================================================== ***/
505
506
/**
507
* A hash table is a data structure that's *unordered*. Instead we have "keys" and "values" where we
508
* computed an address in memory using the key.
509
*
510
* The basic idea is that we have keys that are "hashable" (which we'll get to
511
* in a second) and can be used to add, access, and remove from memory very
512
* efficiently.
513
*
514
* var hashTable = new HashTable();
515
*
516
* hashTable.set('myKey', 'myValue');
517
* hashTable.get('myKey'); // >> 'myValue'
518
*/
519
520
class HashTable {
521
522
/**
523
* Again we're going to use a plain JavaScript array to represent our memory.
524
*/
525
526
constructor() {
527
this.memory = [];
528
}
529
530
/**
531
* In order to store key-value pairs in memory from our hash table we need a
532
* way to take the key and turn it into an address. We do this through an
533
* operation known as "hashing".
534
*
535
* Basically it takes a key and serializes it into a unique number for that
536
* key.
537
*
538
* hashKey("abc") => 96354
539
* hashKey("xyz") => 119193
540
*
541
* You have to be careful though, if you had a really big key you don't want
542
* to match it to a memory address that does not exist.
543
*
544
* So the hashing algorithm needs to limit the size, which means that there
545
* are a limited number of addresses for an unlimited number of values.
546
*
547
* The result is that you can end up with collisions. Places where two keys
548
* get turned into the same address.
549
*
550
* Any real-world hash table implementation would have to deal with this,
551
* however, we are just going to glaze over it and pretend that doesn't happen.
552
*/
553
554
/**
555
* Let's set up our "hashKey" function.
556
*
557
* Don't worry about understanding the logic of this function, just know that
558
* it accepts a string and outputs a (mostly) unique address that we will use
559
* in all of our other functions.
560
*/
561
562
hashKey(key) {
563
let hash = 0;
564
for (let index = 0; index < key.length; index++) {
565
// Oh look– magic.
566
let code = key.charCodeAt(index);
567
hash = ((hash << 5) - hash) + code | 0;
568
}
569
return hash;
570
}
571
572
/**
573
* Next, let's define our "get" function so we have a way of accessing values
574
* by their key.
575
*
576
* HashTable access is constant O(1) - "AWESOME!!"
577
*/
578
579
get(key) {
580
// We start by turning our key into an address.
581
let address = this.hashKey(key);
582
// Then we simply return whatever is at that address.
583
return this.memory[address];
584
}
585
586
/**
587
* We also need a way of adding data before we access it, so we will create
588
* a "set" function that inserts values.
589
*
590
* HashTable setting is constant O(1) - "AWESOME!!"
591
*/
592
593
set(key, value) {
594
// Again we start by turning the key into an address.
595
let address = this.hashKey(key);
596
// Then just set the value at that address.
597
this.memory[address] = value;
598
}
599
600
/**
601
* Finally we just need a way to remove items from our hash table.
602
*
603
* HashTable deletion is constant O(1) - "AWESOME!!"
604
*/
605
606
remove(key) {
607
// As always, we hash the key to get an address.
608
let address = this.hashKey(key);
609
// Then, if it exists, we `delete` it.
610
if (this.memory[address]) {
611
delete this.memory[address];
612
}
613
}
614
}
615
616
/**
617
* ============================================================================
618
* ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
619
* ============================================================================
620
*/
621
622
/**
623
* From this point going forward we are going to stop interacting directly with
624
* memory as the rest of these data structures start to be implemented with
625
* other data structures.
626
*
627
* These data structures focus on doing two things:
628
*
629
* - Organizing data based on how it is used
630
* - Abstracting away implementation details
631
*
632
* These data structures focus on creating an organization that makes sense for
633
* various types of programs. They insert a language that allows you to discuss
634
* more complicated logic. All of this while abstracting away implementation
635
* details so that their implementation can change to be made faster.
636
*/
637
638
/*** ===================================================================== ***\
639
** - STACKS -------------------------------------------------------------- **
640
* ========================================================================= *
641
* _ . - - -- .. _ *
642
* |||| .-' /```\ `'-_ /| *
643
* |||| ( /`` \___/ ```\ ) | | *
644
* \__/ |`"-//..__ __..\\-"`| | | *
645
* || |`"||...__`````__...||"`| | | *
646
* || |`"||...__`````__...||"`| \ | *
647
* || _,.--|`"||...__`````__...||"`|--.,_ || *
648
* || .'` |`"||...__`````__...||"`| `'. || *
649
* || '. `/ |...__`````__...| \ .' || *
650
* || `'-..__ `` ````` `` __..-'` || *
651
* `""---,,,_______,,,---""` *
652
** **
653
\*** ===================================================================== ***/
654
655
/**
656
* Stacks are similar to lists in that they have an order, but they limit you
657
* to only pushing and popping values at the end of the list, which as we saw
658
* before are very fast operations when mapping directly to memory.
659
*
660
* However, Stacks can also be implemented with other data structures in order
661
* to add functionality to them.
662
*
663
* The most common usage of the stacks is in the places where you have one process adding
664
* items to the stack and another process removing them from the end–
665
* prioritizing items added most recently.
666
*/
667
668
class Stack {
669
670
/**
671
* We're going to again be backed by a JavaScript array, but this time it
672
* represents a list like we implemented before rather than memory.
673
*/
674
675
constructor() {
676
this.list = [];
677
this.length = 0;
678
}
679
680
/**
681
* We're going to implement two of the functions from list's "push" and "pop"
682
* which are going to be identical in terms of functionality.
683
*/
684
685
/**
686
* Push to add items to the top of the stack.
687
*/
688
689
push(value) {
690
this.length++;
691
this.list.push(value);
692
}
693
694
/**
695
* And pop to remove items from the top of the stack.
696
*/
697
698
pop() {
699
// Don't do anything if we don't have any items.
700
if (this.length === 0) return;
701
702
// Pop the last item off the end of the list and return the value.
703
this.length--;
704
return this.list.pop();
705
}
706
707
/**
708
* We're also going to add a function in order to view the item at the top of
709
* the stack without removing it from the stack.
710
*/
711
712
peek() {
713
// Return the last item in "items" without removing it.
714
return this.list[this.length - 1];
715
}
716
}
717
718
/*** ===================================================================== ***\
719
** - QUEUES -------------------------------------------------------------- **
720
* ========================================================================= *
721
* /:""| ,@@@@@@. *
722
* |: oo|_ ,@@@@@`oo *
723
* C _) @@@@C _) *
724
* ) / "@@@@ '= *
725
* /`\\ ```)/ *
726
* || | | /`\\ *
727
* || | | || | \ *
728
* ||_| | || | / *
729
* \( ) | ||_| | *
730
* |~~~`-`~~~| |))) | *
731
* (_) | | (_) |~~~/ (_) *
732
* | |`""....__ __....""`| |`""...._|| / __....""`| | *
733
* | |`""....__`````__....""`| |`""....__`````__....""`| | *
734
* | | | ||``` | | ||`|`` | | *
735
* | | |_||__ | | ||_|__ | | *
736
* ,| |, jgs (____)) ,| |, ((;:;:) ,| |, *
737
** `---` `---` `---` **
738
\*** ===================================================================== ***/
739
740
/**
741
* Next, we're going to build a queue which is complementary to stacks. The
742
* difference is that this time you remove items from the start of the queue
743
* rather than the end. Removing the oldest items rather than the most recent.
744
*
745
* Again, because this limits the amount of functionality, there are many
746
* different ways of implementing it. A good way might be to use a linked list
747
* which we will see later.
748
*/
749
750
class Queue {
751
752
/**
753
* Again, our queue is using a JavaScript array as a list rather than memory.
754
*/
755
756
constructor() {
757
this.list = [];
758
this.length = 0;
759
}
760
761
/**
762
* Similar to stacks we're going to define two functions for adding and
763
* removing items from the queue. The first is "enqueue".
764
*
765
* This will push values to the end of the list.
766
*/
767
768
enqueue(value) {
769
this.length++;
770
this.list.push(value);
771
}
772
773
/**
774
* Next is "dequeue", instead of removing the item from the end of the list,
775
* we're going to remove it from the start.
776
*/
777
778
dequeue() {
779
// Don't do anything if we don't have any items.
780
if (this.length === 0) return;
781
782
// Shift the first item off the start of the list and return the value.
783
this.length--;
784
return this.list.shift();
785
}
786
787
/**
788
* Same as stacks we're going to define a "peek" function for getting the next
789
* value without removing it from the queue.
790
*/
791
792
peek() {
793
return this.list[0];
794
}
795
}
796
797
/**
798
* The important thing to note here is that because we used a list to back our
799
* queue it inherits the performance of "shift" which is linear O(N) "OKAY."
800
*
801
* Later we'll see linked lists that will allow us to implement a much faster
802
* Queue.
803
*/
804
805
/**
806
* ============================================================================
807
* ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
808
* ============================================================================
809
*/
810
811
/**
812
* From this point forward we're going to start dealing with data structures
813
* where the values of the data structure reference one another.
814
*
815
* +- Data Structure ---------------------------------------+
816
* | +- Item A ---------------+ +- Item B ---------------+ |
817
* | | Value: 1 | | Value: 2 | |
818
* | | Reference to: (Item B) | | Reference to: (Item A) | |
819
* | +------------------------+ +------------------------+ |
820
* +--------------------------------------------------------+
821
*
822
* The values inside the data structure become their own mini data structures
823
* in that they contain a value along with additional information including
824
* references to other items within the overall data structure.
825
*
826
* You'll see what I mean by this in a second.
827
*/
828
829
/*** ===================================================================== ***\
830
** - GRAPHS -------------------------------------------------------------- **
831
* ========================================================================= *
832
* *
833
* | RICK ASTLEY'S NEVER GONNA... *
834
* | +-+ *
835
* | +-+ |-| [^] - GIVE YOU UP *
836
* | |^| |-| +-+ [-] - LET YOU DOWN *
837
* | |^| |-| +-+ |*| [/] - RUN AROUND AND DESERT YOU *
838
* | |^| |-| +-+ |\| |*| [\] - MAKE YOU CRY *
839
* | |^| |-| |/| |\| +-+ |*| [.] - SAY GOODBYE *
840
* | |^| |-| |/| |\| |.| |*| [*] - TELL A LIE AND HURT YOU *
841
* | |^| |-| |/| |\| |.| |*| *
842
* +-------------------------------- *
843
** **
844
\*** ===================================================================== ***/
845
846
/**
847
* Contrary to the ascii art above, a graph is not a visual chart of some sort.
848
*
849
* Instead imagine it like this:
850
*
851
* A –→ B ←–––– C → D ↔ E
852
* ↑ ↕ ↙ ↑ ↘
853
* F –→ G → H ← I ––––→ J
854
* ↓ ↘ ↑
855
* K L
856
*
857
* We have a bunch of "nodes" (A, B, C, D, ...) that are connected with lines.
858
*
859
* These nodes are going to look like this:
860
*
861
* Node {
862
* value: ...,
863
* lines: [(Node), (Node), ...]
864
* }
865
*
866
* The entire graph will look like this:
867
*
868
* Graph {
869
* nodes: [
870
* Node {...},
871
* Node {...},
872
* ...
873
* ]
874
* }
875
*/
876
877
class Graph {
878
879
/**
880
* We'll hold onto all of our nodes in a regular JavaScript array. Not
881
* because there is any particular order to the nodes but because we need a
882
* way to store references to everything.
883
*/
884
885
constructor() {
886
this.nodes = [];
887
}
888
889
/**
890
* We can start to add values to our graph by creating nodes without any
891
* lines.
892
*/
893
894
addNode(value) {
895
return this.nodes.push({
896
value,
897
lines: []
898
});
899
}
900
901
/**
902
* Next we need to be able to lookup nodes in the graph. Most of the time
903
* you'd have another data structure on top of a graph in order to make
904
* searching faster.
905
*
906
* But for our case, we're simply going to search through all of the nodes to find
907
* the one with the matching value. This is a slower option, but it works for
908
* now.
909
*/
910
911
find(value) {
912
return this.nodes.find(node => {
913
return node.value === value;
914
});
915
}
916
917
/**
918
* Next we can connect two nodes by making a "line" from one to the other.
919
*/
920
921
addLine(startValue, endValue) {
922
// Find the nodes for each value.
923
let startNode = this.find(startValue);
924
let endNode = this.find(endValue);
925
926
// Freak out if we didn't find one or the other.
927
if (!startNode || !endNode) {
928
throw new Error('Both nodes need to exist');
929
}
930
931
// And add a reference to the endNode from the startNode.
932
startNode.lines.push(endNode);
933
}
934
}
935
936
/**
937
* Finally you can use a graph like this:
938
*
939
* var graph = new Graph();
940
* graph.addNode(1);
941
* graph.addNode(2);
942
* graph.addLine(1, 2);
943
* var two = graph.find(1).lines[0];
944
*
945
* This might seem like a lot of work to do very little, but it's actually a
946
* quite powerful pattern, especially for finding sanity in complex programs.
947
*
948
* They do this by optimizing for the connections between data rather than
949
* operating on the data itself. Once you have one node in the graph, it's
950
* extremely simple to find all the related items in the graph.
951
*
952
* Tons of things can be represented this way, users with friends, the 800
953
* transitive dependencies in a node_modules folder, the internet itself is a
954
* graph of webpages connected together by links.
955
*/
956
957
/*** ===================================================================== ***\
958
** - LINKED LISTS -------------------------------------------------------- **
959
* ========================================================================= *
960
* _______________________ *
961
* ()=(_______________________)=() ,-----------------,_ *
962
* | | ," ", *
963
* | ~ ~~~~~~~~~~~~~ | ,' ,---------------, `, *
964
* | ,----------------------------, ,----------- *
965
* | ~ ~~~~~~~~ | | | *
966
* | `----------------------------' `----------- *
967
* | ~ ~~~~~~~~~~~~~ | `, `----------------' ,' *
968
* | | `, ,' *
969
* |_____________________| `------------------' *
970
* ()=(_______________________)=() *
971
** **
972
\*** ===================================================================== ***/
973
974
/**
975
* Next we're going to see how a graph-like structure can help optimize ordered
976
* lists of data.
977
*
978
* Linked lists are a very common data structure that is often used to
979
* implement other data structures because of its ability to efficiently add
980
* items to the start, middle, and end.
981
*
982
* The basic idea of a linked list is similar to a graph. You have nodes that
983
* point to other nodes. They look sorta like this:
984
*
985
* 1 -> 2 -> 3 -> 4 -> 5
986
*
987
* Visualizing them as a JSON-like structure looks like this:
988
*
989
* {
990
* value: 1,
991
* next: {
992
* value: 2,
993
* next: {
994
* value: 3,
995
* next: {...}
996
* }
997
* }
998
* }
999
*/
1000
1001
class LinkedList {
1002
1003
/**
1004
* Unlike a graph, a linked list has a single node that starts off the entire
1005
* chain. This is known as the "head" of the linked list.
1006
*
1007
* We're also going to track the length.
1008
*/
1009
1010
constructor() {
1011
this.head = null;
1012
this.length = 0;
1013
}
1014
1015
/**
1016
* First we need a way to retrieve a value in a given position.
1017
*
1018
* This works differently than normal lists as we can't just jump to the
1019
* correct position. Instead, we need to move through the individual nodes.
1020
*/
1021
1022
get(position) {
1023
// Throw an error if position is greater than the length of the LinkedList
1024
if (position >= this.length) {
1025
throw new Error('Position outside of list range');
1026
}
1027
1028
// Start with the head of the list.
1029
let current = this.head;
1030
1031
// Slide through all of the items using node.next until we reach the
1032
// specified position.
1033
for (let index = 0; index < position; index++) {
1034
current = current.next;
1035
}
1036
1037
// Return the node we found.
1038
return current;
1039
}
1040
1041
/**
1042
* Next we need a way to add nodes to the specified position.
1043
*
1044
* We're going for a generic add method that accepts a value and a position.
1045
*/
1046
1047
add(value, position) {
1048
// First create a node to hold our value.
1049
let node = {
1050
value,
1051
next: null
1052
};
1053
1054
// We need to have a special case for nodes being inserted at the head.
1055
// We'll set the "next" field to the current head and then replace it with
1056
// our new node.
1057
if (position === 0) {
1058
node.next = this.head;
1059
this.head = node;
1060
1061
// If we're adding a node in any other position we need to splice it in
1062
// between the current node and the previous node.
1063
} else {
1064
// First, find the previous node and the current node.
1065
let prev = this.get(position - 1);
1066
let current = prev.next;
1067
// Then insert the new node in between them by setting its "next" field
1068
// to the current node and updating the previous node's "next" field to
1069
// the new one.
1070
node.next = current;
1071
prev.next = node;
1072
}
1073
1074
// Finally just increment the length.
1075
this.length++;
1076
}
1077
1078
/**
1079
* The last method we need is a remove method. We're just going to look up a
1080
* node by its position and splice it out of the chain.
1081
*/
1082
1083
remove(position) {
1084
// We should not be able to remove from an empty list
1085
if (!this.head) {
1086
throw new Error('Removing from empty list')
1087
}
1088
// If we're removing the first node we simply need to set the head to the
1089
// next node in the chain
1090
if (position === 0) {
1091
this.head = this.head.next;
1092
1093
// For any other position, we need to look up the previous node and set it
1094
// to the node after the current position.
1095
} else {
1096
let prev = this.get(position - 1);
1097
prev.next = prev.next.next;
1098
}
1099
1100
// Then we just decrement the length.
1101
this.length--;
1102
}
1103
}
1104
1105
/**
1106
* ============================================================================
1107
* ,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
1108
* ============================================================================
1109
*/
1110
1111
/**
1112
* The remaining two data structures we are going to cover are both in the
1113
* "tree" family.
1114
*
1115
* Much like real life, there are many different types of tree data structures.
1116
*
1117
* Binary Trees:
1118
* AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree,
1119
* left child/right sibling tree, order statistic tree, Pagoda, ...
1120
*
1121
* B Trees:
1122
* B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree, ...
1123
*
1124
* Heaps:
1125
* Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo
1126
* Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap, ...
1127
*
1128
* Trees:
1129
* Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie, ...
1130
*
1131
* Multi-way Trees:
1132
* Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree, ...
1133
*
1134
* Space Partitioning Trees:
1135
* Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree,
1136
* Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree, ...
1137
*
1138
* Application-Specific Trees:
1139
* Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree, ...
1140
*
1141
* Little did you know you'd be studying dendrology today... and that's not even
1142
* all of them. But don't let any of this scare you, most of those don't matter
1143
* at all. There were just a lot of Computer Science PhDs who had something to
1144
* prove.
1145
*
1146
* Trees are much like graphs or linked lists except they are "unidirectional".
1147
* All this means is that they can't have loops of references.
1148
*
1149
* Tree: Not a Tree:
1150
*
1151
* A A
1152
* ↙ ↘ ↗ ↘
1153
* B C B ←–––– C
1154
*
1155
* If you can draw a loop between connected nodes in a tree... well, you don't
1156
* have a tree.
1157
*
1158
* Trees have many different uses, they can be used to optimize searching or
1159
* sorting. They can organize programs better. They can give you a
1160
* representation that is easier to work with.
1161
*/
1162
1163
/*** ===================================================================== ***\
1164
** - TREES --------------------------------------------------------------- **
1165
* ========================================================================= *
1166
* ccee88oo \ | / *
1167
* C8O8O8Q8PoOb o8oo '-.;;;.-, ooooO8O8QOb o8bDbo *
1168
* dOB69QO8PdUOpugoO9bD -==;;;;;==-aadOB69QO8PdUOpugoO9bD *
1169
* CgggbU8OU qOp qOdoUOdcb .-';;;'-. CgggOU ddqOp qOdoUOdcb *
1170
* 6OuU /p u gcoUodpP / | \ jgs ooSec cdac pdadfoof *
1171
* \\\// /douUP ' \\\d\\\dp/pddoo *
1172
* \\\//// \\ \\//// *
1173
* |||/\ \\/// *
1174
* |||\/ |||| *
1175
* ||||| /||| *
1176
** .............//||||\.......................//|||\\..................... **
1177
\*** ===================================================================== ***/
1178
1179
/**
1180
* We'll start off with an extremely simple tree structure. It doesn't have any
1181
* special rules to it and looks something like this:
1182
*
1183
* Tree {
1184
* root: {
1185
* value: 1,
1186
* children: [{
1187
* value: 2,
1188
* children: [...]
1189
* }, {
1190
* value: 3,
1191
* children: [...]
1192
* }]
1193
* }
1194
* }
1195
*/
1196
1197
class Tree {
1198
1199
/**
1200
* The tree has to start with a single parent, the "root" of the tree.
1201
*/
1202
1203
constructor() {
1204
this.root = null;
1205
}
1206
1207
/**
1208
* We need a way to traverse our tree and call a function on each node in the
1209
* tree.
1210
*/
1211
1212
traverse(callback) {
1213
// We'll define a walk function that we can call recursively on every node
1214
// in the tree.
1215
function walk(node) {
1216
// First call the callback on the node.
1217
callback(node);
1218
// Then recursively call the walk function on all of its children.
1219
node.children.forEach(walk);
1220
}
1221
1222
// Now kick the traversal process off.
1223
walk(this.root);
1224
}
1225
1226
/**
1227
* Next we need a way to add nodes to our tree.
1228
*/
1229
1230
add(value, parentValue) {
1231
let newNode = {
1232
value,
1233
children: []
1234
};
1235
1236
// If there is no root, just set it to the new node.
1237
if (this.root === null) {
1238
this.root = newNode;
1239
return;
1240
}
1241
1242
// Otherwise traverse the entire tree and find a node with a matching value
1243
// and add the new node to its children.
1244
this.traverse(node => {
1245
if (node.value === parentValue) {
1246
node.children.push(newNode);
1247
}
1248
});
1249
}
1250
}
1251
1252
/**
1253
* This is one of the most basic trees you could have and is probably only
1254
* useful if the data you are representing actually resembles a tree.
1255
*
1256
* But with some extra rules, a tree can serve a lot of different purposes.
1257
*/
1258
1259
/*** ===================================================================== ***\
1260
** - BINARY SEARCH TREES ------------------------------------------------- **
1261
* ========================================================================= *
1262
* 0 0 1 0 1 0 0 1 0 1 1 1 0 1 ,@@@@@@@@@@@@@@, 0 0 1 0 1 0 0 1 0 1 1 1 0 *
1263
* 0 1 0 1 0 1 0 1 1 0 1 1 0 @@` '@@ 0 1 0 1 0 1 1 0 1 0 1 0 *
1264
* 1 1 0 0 0 1 0 0 1 1 1 0 @@` 8O8PoOb o8o '@@ 0 0 1 0 0 1 0 0 1 1 1 *
1265
* 0 0 1 1 0 1 0 1 0 0 0 @@ dOB69QO8PdUgoO9bD @@ 1 0 1 1 0 1 0 1 0 0 *
1266
* ===================== @@ CgbU8OU qOp qOdOdcb @@ 0 1 1 0 1 0 1 0 1 0 *
1267
* @@ 6OU /p u gcoUpP @@ 1 0 1 1 0 1 0 0 1 1 *
1268
* ===================== @@ \\// /doP @@ 0 1 1 0 0 1 0 0 1 0 *
1269
* 1 1 0 0 1 1 0 1 1 0 0 @@ \\// @@ 1 0 1 0 0 1 1 0 1 1 *
1270
* 0 1 1 0 1 0 1 1 0 1 1 0 @@, ||| ,@@ 0 1 1 0 1 1 0 0 1 0 1 *
1271
* 1 0 1 0 1 1 0 0 1 0 0 1 0 @@, //|\ ,@@ 0 1 0 1 0 1 1 0 0 1 1 0 *
1272
** 1 0 1 0 0 1 1 0 1 0 1 0 1 `@@@@@@@@@@@@@@' 0 1 1 1 0 0 1 0 1 0 1 1 **
1273
\*** ===================================================================== ***/
1274
1275
/**
1276
* Binary search trees are a fairly common form of tree for their ability to
1277
* efficiently access, search, insert, and delete values all while keeping them
1278
* in a sorted order.
1279
*
1280
* Imagine taking a sequence of numbers:
1281
*
1282
* 1 2 3 4 5 6 7
1283
*
1284
* And turning it into a tree starting from the center.
1285
*
1286
* 4
1287
* / \
1288
* 2 6
1289
* / \ / \
1290
* 1 3 5 7
1291
* -^--^--^--^--^--^--^-
1292
* 1 2 3 4 5 6 7
1293
*
1294
* This is how a binary tree works. Each node can have two children:
1295
*
1296
* - Left: Less than parent node's value.
1297
* - Right: Greater than parent node's value.
1298
*
1299
* > Note: In order to make this work all values must be unique in the tree.
1300
*
1301
* This makes the traversal to find a value very efficient. Say we're trying to
1302
* find the number 5 in our tree:
1303
*
1304
* (4) <--- 5 > 4, so move right.
1305
* / \
1306
* 2 (6) <--- 5 < 6, so move left.
1307
* / \ / \
1308
* 1 3 (5) 7 <--- We've reached 5!
1309
*
1310
* Notice how we only had to do 3 checks to reach the number 5. If we were to
1311
* expand this tree to 1000 items. We'd go:
1312
*
1313
* 500 -> 250 -> 125 -> 62 -> 31 -> 15 -> 7 -> 3 -> 4 -> 5
1314
*
1315
* Only 10 checks for 1000 items!
1316
*
1317
* The other important thing about binary search trees is that they are similar
1318
* to linked lists in the sense that you only need to update the immediately
1319
* surrounding items when adding or removing a value.
1320
*/
1321
1322
class BinarySearchTree {
1323
1324
/**
1325
* Same as the previous Tree, we need to have a "root" of the binary search
1326
* tree.
1327
*/
1328
1329
constructor() {
1330
this.root = null;
1331
}
1332
1333
/**
1334
* In order to test if the value exists in the tree, we first need to search
1335
* through the tree.
1336
*/
1337
1338
contains(value) {
1339
// We start at the root.
1340
let current = this.root;
1341
1342
// We're going to keep running as long as we have another node to visit.
1343
// If we reach a `left` or `right` that is `null` then this loop ends.
1344
while (current) {
1345
1346
// If the value is greater than the current.value we move to the right
1347
if (value > current.value) {
1348
current = current.right;
1349
1350
// If the value is less than the current.value we move to the left.
1351
} else if (value < current.value) {
1352
current = current.left;
1353
1354
// Otherwise we must be equal values and we return true.
1355
} else {
1356
return true;
1357
}
1358
}
1359
1360
// If we haven't matched anything then we return false.
1361
return false;
1362
}
1363
1364
/**
1365
* In order to add items to this tree we are going to do the same traversal
1366
* as before, bouncing between left and right nodes depending on them being
1367
* less than or greater than the value we're adding.
1368
*
1369
* However, this time when we reach a `left` or `right` that is `null` we're
1370
* going to add a new node in that position.
1371
*/
1372
1373
add(value) {
1374
// First let's setup our node.
1375
let node = {
1376
value: value,
1377
left: null,
1378
right: null
1379
};
1380
1381
// Special case for when there isn't any root node and we just need to add
1382
// one.
1383
if (this.root === null) {
1384
this.root = node;
1385
return;
1386
}
1387
1388
// We start at the root.
1389
let current = this.root;
1390
1391
// We're going to loop until we've either added our item or discovered it
1392
// already exists in the tree.
1393
while (true) {
1394
1395
// If the value is greater than the current.value we move to the right.
1396
if (value > current.value) {
1397
1398
// If `right` does not exist, set it to our node, and stop traversing.
1399
if (!current.right) {
1400
current.right = node;
1401
break;
1402
}
1403
1404
// Otherwise just move on to the right node.
1405
current = current.right;
1406
1407
// If the value is less than the current.value we move to the left.
1408
} else if (value < current.value) {
1409
1410
// If `left` does not exist, set it to our node, and stop traversing.
1411
if (!current.left) {
1412
current.left = node;
1413
break;
1414
}
1415
1416
// Otherwise just move on to the left node.
1417
current = current.left;
1418
1419
// If the number isn't less than or greater, then it must be the same and
1420
// we don't do anything.
1421
} else {
1422
break;
1423
}
1424
}
1425
}
1426
}
1427
1428
/*** ===================================================================== ***\
1429
** - YOU REACHED THE END! ------------------------------------------------ **
1430
* ========================================================================= *
1431
* .''. *
1432
* .''. *''* :_\/_: . *
1433
* :_\/_: . .:.*_\/_* : /\ : .'.:.'. *
1434
* .''.: /\ : _\(/_ ':'* /\ * : '..'. -=:o:=- *
1435
* :_\/_:'.:::. /)\*''* .|.* '.\'/.'_\(/_'.':'.' *
1436
* : /\ : ::::: '*_\/_* | | -= o =- /)\ ' * *
1437
* '..' ':::' * /\ * |'| .'/.\'. '._____ *
1438
* * __*..* | | : |. |' .---"| *
1439
* _* .-' '-. | | .--'| || | _| | *
1440
* .-'| _.| | || '-__ | | | || | *
1441
* |' | |. | || | | | | || | *
1442
* _____________| '-' ' "" '-' '-.' '` |____________ *
1443
** jgs~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ **
1444
\*** ===================================================================== ***/
1445
1446
/**
1447
* I know that was probably a bit dense, but hopefully it gave you a good
1448
* amount of knowledge. If you enjoyed it, would you mind giving the repo a
1449
* star and follow me on twitter (@thejameskyle)?
1450
*
1451
* You can also check out my other code walkthrough, "The Super Tiny Compiler"
1452
* here ------> https://github.com/thejameskyle/the-super-tiny-compiler
1453
*/
1454
1455
// Just exporting everything for the tests...
1456
module.exports = {
1457
List,
1458
HashTable,
1459
Stack,
1460
Queue,
1461
Graph,
1462
LinkedList,
1463
Tree,
1464
BinarySearchTree
1465
};
Copied!
Last modified 14h ago
Copy link
Edit on GitHub